1. Field of the Invention
The present invention relates to routing connections in a telecommunications network, and, more particularly, to capacity allocation for paths through nodes of the network when path lengths are constrained.
2. Description of the Related Art
In interconnected communications networks, users establish connections between a source node and a destination node with a stream of data that is transferred through the network over a network path. The data of one or more connections constitutes traffic over the network. Optical networks are typically characterized by a set of micro-mechanical optical switches (i.e., nodes) connected via optical links. Packet networks (which may be implemented using optical networks) are typically characterized by routers (also considered nodes) interconnected by electrical or optical links. A network path for a connection between a given source-destination (node) pair is defined by a set of nodes (the source and destination node pair and any intermediate nodes) interconnected by a set of links coupled to the nodes carrying the data stream, or flow, of the connection.
Capacity allocation in networks assigns traffic of connections to certain paths through the network based on the capacity of network nodes and links. For example, such capacity may be the number of connections supported at input or output interfaces of the node, or may be bandwidth of a link. In addition, Quality of Service (QoS) guarantees, such as minimum delay, packet loss, or bandwidth guarantees, may be accounted for with an effective bandwidth of the packet loss, or bandwidth guarantees, may be accounted for with an effective bandwidth of the links. For capacity allocation and provisioning purposes, the amount of traffic that may be routed between sources and destinations in a given network is desirably determined based on some method that optimizes the available capacity for the network while meeting QoS requirements of the connections routed over the network. One form of capacity allocation issue arises in networks where some of the traffic has to be routed on paths with specified bounds on their lengths. These allocation issues arise in both packet networks and optical networks.
Path-length bounds are an important constraint for wavelength routing in optical networks because the optical signal attenuates as it traverses fiber links, which is desirably accounted for when routing the connection. Optical signal attenuation is a function of the type of fiber as well as the wavelength of the optical signal. As the optical signal traverses a link, it is typically amplified periodically using an In-Line Optical Amplifier, also referred to as the 1R (re-amplification) function. Amplification boosts the optical signal. When the optical signal traverses longer distances, it may be regenerated using an Optical-Electrical-Optical regenerator, also referred to as the 3R (retime, reshape, re-amplify) function. The optical regenerators are expensive components in an optical network. Thus, to minimize regeneration of the optical signal, the length of the physical path traversed by the optical signal is desirably kept to a minimum, forming a path-length constraint for the paths traversed by the signal.
Path-length constraints in packet networks usually arise as restrictions on the number of hops in the path traversed by the packet. Each time a router processes a packet, the router introduces delay and jitter. As the length of the path increases, delay and jitter increases.
Path-length constraints may also be employed to model routing when link error rates are known and the path(s) for a connection desirably meet certain error rate constraints. For example, if link loss rates are known, path-length constraints are used to ensure that the path loss for a given connection is within some predetermined value. In addition, path-length constraints may be employed to route connections with link preferences taken into account. In general, such modeling associates an auxiliary preference “cost” for each link, and the connections are then routed on paths that not only meet specified length constraints but also meet constraints on the preference cost.